package com.jiang.daily.Q3291;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/17 23:25
 */
class Solution {
    public int minValidStrings(String[] words, String target) {
        int len = target.length();
        // back[i] 表示target能匹配每一个单词的最长前缀
        int[] back = new int[len];
        for (String word: words) {
            int[] next = build_next(word, target);
            int w_len = word.length();
            for(int i = 0; i < len; i++) {
                back[i] = Math.max(back[i], next[w_len + 1 + i]);
            }
        }
        //  dp[i] 表示形成前 n 个字母需要的最少字符串数
        int[] dp = new int[len + 1];
        Arrays.fill(dp, 1, len + 1, (int)1e9);
        for (int i = 1; i < len + 1; i++) {
            // i - back[i - 1] 表示第i个字母 与 这个字母的最长前缀之差， 如果等于0，表示前面全部单词都能用一个字符串表示，是第一个字符串； 等于i 表示这个字母没有word匹配； 等于其它的，就表示前back[i - 1]个单词都可以用一个字符串表示, 那么我们只需要看dp[i - back[i - 1]]要几个字符串表示 在加一
            dp[i] = dp[i - back[i - 1]] + 1;
            // 如果最小有效字符串数大于目标字符串的长度，则返回-1
            if (dp[i] > len) {
                return -1;
            }
        }
        // 返回dp数组中最后一个元素，即最小有效字符串数
        return dp[len];
    }

    // KMP算法得到next数组（本质是寻找子串中相同前后缀的长度）这里我们要将word和target拼接，求出target能匹配word的前缀长度
    private int[] build_next(String word, String target) {
        // 防止target自我匹配
        String s = word + "#" + target;
        int len = s.length();
        int[] next = new int[len];
        for (int i = 1; i < len; i++) {
            int j = next[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

}
